// 提交链接 https://leetcode.cn/problems/sum-of-distances-in-tree/submissions/569579400/
// 834. 树中距离之和
// 完成日期： 2024.10.7
// 换根dp
class Solution {
public:
    unordered_map<int, vector<int>> ma;
    int dis[30005], num[30005], dp[300005];
    vector<int> sumOfDistancesInTree(int n, vector<vector<int>>& edges) {
        for (auto& x : edges)
        {
            ma[x[0]].push_back(x[1]);
            ma[x[1]].push_back(x[0]);
        }
        dfs1(0, -1);
        dfs2(0, -1, n);
        vector<int> ans;
        for (int i = 0; i < n; i++) ans.push_back(dp[i]);
        return ans; 
    }
    pair<int, int> dfs1(int pos, int pre)
    {
        int ans1 = 0, ans2 = 1;
        for (auto& x : ma[pos])
        {
            if (x == pre) continue;
            pair<int, int> temp = dfs1(x, pos);
            ans1 += temp.first + temp.second;
            ans2 += temp.second;
        }
        dis[pos] = ans1;
        num[pos] = ans2;
        return pair<int, int>(ans1, ans2);
    }
    void dfs2(int pos, int pre, int& n)
    {
        if (!pos) dp[pos] = dis[pos];
        else dp[pos] = dp[pre] - 2 * num[pos] + n;
        for (auto& x : ma[pos])
        {
            if (x == pre) continue;
            dfs2(x, pos, n);
        }
        return;
    }
};